/*
 * trans.c - 矩阵转置B=A^T
 *每个转置函数都必须具有以下形式的原型：
 *void trans（int M，int N，int a[N][M]，int B[M][N]）；
 *通过计算，块大小为32字节的1KB直接映射缓存上的未命中数来计算转置函数。
 */
#include <stdio.h>
#include "cachelab.h"
int is_transpose(int M, int N, int A[N][M], int B[M][N]);
char transpose_submit_desc[] = "Transpose submission"; // 请不要修改“Transpose_submission”

void transpose_submit(int M, int N, int A[N][M], int B[M][N])
{
    int i, j, k, l, t0, t1, t2, t3, t4, t5, t6, t7;

    for (l = 0; l < N / 8; l++)
    {
        for (k = 0; k < M / 8; k++)
        {
            for (i = 0; i < 4; i++)
            {
                t0 = A[l * 8 + i][k * 8];
                t1 = A[l * 8 + i][k * 8 + 1];
                t2 = A[l * 8 + i][k * 8 + 2];
                t3 = A[l * 8 + i][k * 8 + 3];
                t4 = A[l * 8 + i][k * 8 + 4];
                t5 = A[l * 8 + i][k * 8 + 5];
                t6 = A[l * 8 + i][k * 8 + 6];
                t7 = A[l * 8 + i][k * 8 + 7];
                B[k * 8][l * 8 + i] = t0;
                B[k * 8 + 1][l * 8 + i] = t1;
                B[k * 8 + 2][l * 8 + i] = t2;
                B[k * 8 + 3][l * 8 + i] = t3;
                B[k * 8][l * 8 + i + 4] = t4;
                B[k * 8 + 1][l * 8 + i + 4] = t5;
                B[k * 8 + 2][l * 8 + i + 4] = t6;
                B[k * 8 + 3][l * 8 + i + 4] = t7;
            }
            for (i = 0; i < 4; i++)
            {
                t0 = B[k * 8 + i][l * 8 + 4];
                t1 = B[k * 8 + i][l * 8 + 5];
                t2 = B[k * 8 + i][l * 8 + 6];
                t3 = B[k * 8 + i][l * 8 + 7];
                t4 = A[l * 8 + 4][k * 8 + i];
                t5 = A[l * 8 + 5][k * 8 + i];
                t6 = A[l * 8 + 6][k * 8 + i];
                t7 = A[l * 8 + 7][k * 8 + i];
                B[k * 8 + i][l * 8 + 4] = t4;
                B[k * 8 + i][l * 8 + 5] = t5;
                B[k * 8 + i][l * 8 + 6] = t6;
                B[k * 8 + i][l * 8 + 7] = t7;
                t4 = A[l * 8 + 4][k * 8 + i + 4];
                t5 = A[l * 8 + 5][k * 8 + i + 4];
                t6 = A[l * 8 + 6][k * 8 + i + 4];
                t7 = A[l * 8 + 7][k * 8 + i + 4];

                B[k * 8 + i + 4][l * 8] = t0;
                B[k * 8 + i + 4][l * 8 + 1] = t1;
                B[k * 8 + i + 4][l * 8 + 2] = t2;
                B[k * 8 + i + 4][l * 8 + 3] = t3;
                B[k * 8 + i + 4][l * 8 + 4] = t4;
                B[k * 8 + i + 4][l * 8 + 5] = t5;
                B[k * 8 + i + 4][l * 8 + 6] = t6;
                B[k * 8 + i + 4][l * 8 + 7] = t7;
            }
        }
        for (j = k * 8; j < M; j++)
        {
            t0 = A[l * 8][j];
            t1 = A[l * 8 + 1][j];
            t2 = A[l * 8 + 2][j];
            t3 = A[l * 8 + 3][j];
            t4 = A[l * 8 + 4][j];
            t5 = A[l * 8 + 5][j];
            t6 = A[l * 8 + 6][j];
            t7 = A[l * 8 + 7][j];

            B[j][l * 8] = t0;
            B[j][l * 8 + 1] = t1;
            B[j][l * 8 + 2] = t2;
            B[j][l * 8 + 3] = t3;
            B[j][l * 8 + 4] = t4;
            B[j][l * 8 + 5] = t5;
            B[j][l * 8 + 6] = t6;
            B[j][l * 8 + 7] = t7;
        }
    }
    if (l * 8 < N)
    {
        for (j = 0; j < M; j++)
        {
            for (i = l * 8; i < N; i++)
            {
                t0 = A[i][j];
                B[j][i] = t0;
            }
        }
    }
}

/*
 * 我们在下面定义了一个简单的方法来帮助您开始，您可以根据下面的例子把上面值置补充完整。
 */

/*
 * 简单的基线转置功能，未针对缓存进行优化。
 */
char trans_desc[] = "Simple row-wise scan transpose";
void trans(int M, int N, int A[N][M], int B[M][N])
{
    int i, j, tmp;

    for (i = 0; i < N; i++)
    {
        for (j = 0; j < M; j++)
        {
            tmp = A[i][j];
            B[j][i] = tmp;
        }
    }
}

/*
 * registerFunctions-此函数向驱动程序注册转置函数。
 *在运行时，驱动程序将评估每个注册的函数并总结它们的性能。这是一种试验不同转置策略的简便方法。
 */
void registerFunctions()
{
    /* 注册解决方案函数  */
    registerTransFunction(transpose_submit, transpose_submit_desc);

    /* 注册任何附加转置函数 */
    registerTransFunction(trans, trans_desc);
}

/*
 * is_transpose - 函数检查B是否是A的转置。在从转置函数返回之前，可以通过调用它来检查转置的正确性。
 */
int is_transpose(int M, int N, int A[N][M], int B[M][N])
{
    int i, j;

    for (i = 0; i < N; i++)
    {
        for (j = 0; j < M; ++j)
        {
            if (A[i][j] != B[j][i])
            {
                return 0;
            }
        }
    }
    return 1;
}
